Stephen Cook

概述

美国-加拿大计算机科学家（1939–2023），1971年发表论文《The Complexity of Theorem-Proving Procedures》，定义了 NP 完全性概念并证明了 SAT 是第一个 NP 完全问题。1982年因计算复杂度理论的开创性贡献获得 ACM 图灵奖。

关键内容

Cook 1971年论文

• 在 STOC 会议上发表了仅八页的论文
• 定义了 NP 完全性概念
• 证明了布尔可满足性问题（SAT）是 NP 完全的
• 证明了即使 CNF 形式的 SAT（CNF-SAT）也是 NP 完全的

证明的核心洞察

将非确定性图灵机的计算过程编码为布尔公式： - 用计算表（computation tableau）描述图灵机的运行 - 为表格的每个单元格引入布尔变量 - 将初始条件、合法性约束、转移规则和接受条件表达为 CNF 子句 - 证明了 M 接受 x 当且仅当所构造的公式可满足

图灵奖（1982）

授奖理由是"在计算复杂度理论方面的开创性贡献"。

后续影响

• 启发了 Karp（1972）证明21个经典组合问题的 NP 完全性
• 为 P vs NP 问题（千禧年数学问题，悬赏100万美元）奠定基础
• 改变了算法研究的方法论：从"盲目寻找高效算法"到"先证明复杂度再选择策略"

来源

• raw/books/计算机科学/08-cook-np-completeness.md

相关

• Cook NP 完全性论文 — 1971年发表
• NP 完全性 — 定义
• Cook-Levin 定理 — 证明
• P vs NP — 奠定的问题
• Leonid Levin — 独立发现者
• Richard Karp — 拓展者